(defun primep(n)
  (cond 
    ((< n 0) (primep (- n)))
    ((<= n 3) t)
    ((zerop (mod n 2)) nil)
    (t (loop 
	  for i = 3 then (+ 2 i) 
	  with lim = (sqrt n) 
	  while (<= i lim) 
	  when (zerop (mod n i)) do (return nil) 
	  finally (return t)))))

(defun factors (n)
  (loop 
     with nf = n
     with facts = ()
     for i = 2 then  (1+ i)
     when (zerop (mod nf i))
     do (setq facts (cons i facts)) do (loop while (zerop (mod nf i)) do (setq nf (/ nf i)))
     until (= nf 1)
     finally (return facts)))

(defun get-list(max)
  (cons '1 (cons '2 (loop for i = 3 then (+ i 2) until (> i max)  collect i))))

(defun remove-multiples (list no)
  (delete-if #'(lambda (x) (and (not (= x no)) (zerop (mod x no)))) list))

(defun erostene(max)
  (loop with list = (get-list max)
       for i from 3 to max do (remove-multiples list i)
       finally (return list)))

(defun factors (n)
  (loop 
     with nf = n
     with facts = ()
     for i = 2 then  (1+ i)
     when (zerop (mod nf i))
     do (loop while (zerop (mod nf i)) do (setq nf (/ nf i)) do (setq facts (cons i facts)))
     until (= nf 1)
     finally (return facts)))


(defun phi(n)
  (1+ (loop for i from 2 to (1- n) 
	 with factors = (factors n) 
	 when () count i)))

(defun n-over-phi(n)
  (/ n (phi n)))

(defun n-over-phi (n)
  (/ 1 (reduce #'* (mapcar #'(lambda (x) (- 1 (/ 1 x))) (factors n)))))

(defun maximize-n-over-phi(max)
  (loop for i from 3 to max 
     with max = (n-over-phi 2) 
     with idx = 2
     for noverphi = (n-over-phi i)
     when (< max noverphi)
     do (and (setf max noverphi)
	     (setf idx i))
     finally (return idx)))